
package main.old.new_2023.last.month_8;


import java.util.*;

/**
 * @Description:
 * todo 1654. 到家的最少跳跃次数
 * 有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。
 * 跳蚤跳跃的规则如下：
 * 它可以 往前 跳恰好 a 个位置（即往右跳）。
 * 它可以 往后 跳恰好 b 个位置（即往左跳）。
 * 它不能 连续 往后跳 2 次。
 * 它不能跳到任何 forbidden 数组中的位置。
 * 跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。
 *
 * 给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，
 * 请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。
 *
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0829 {

    //到家的最少跳跃次数
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        // 记录禁止停留的位置
        Set<Integer> forbiddenSet = new HashSet<>();
        for (int position : forbidden) forbiddenSet.add(position);
        // 确定跳动的范围，下界限是0，上界限是max(max(forbidden)+a,x)+b
        // 此题难点：如何确定上界限，可看题解中的证明
        int lower = 0, upper = Math.max(Arrays.stream(forbidden).max().getAsInt() + a, x) + b;
        // 队列动态增加，使用数组存储【位置、方向、步骤计数器】
        Queue<int[]> queue = new ArrayDeque<>();
        // 默认值，因为位置初始化为0，已经抵达下限，则方向默认值为1即前进，步骤计数器为0
        queue.offer(new int[]{0, 1, 0});
        // 记录已经运动过的位置，方便裁剪
        Set<Integer> visited = new HashSet<>();
        visited.add(0);
        // 遍历队列元素
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int position = arr[0], direction = arr[1], step = arr[2];
            // 终止条件之一，找到相等情况，直接返回步骤计数器
            if (position == x) return step;
            /**
             * 此时有三种情况：
             * 1、前进的可能
             * 2、后退的可能
             * 3、无法前进或后退，则在下个循环退出
             */
            // 临时变量，记录位置
            int nextPosition = position + a;
            // 临时变量，记录方向
            int nextDirection = 1;
            // 判断位置是否在上下界限中，判断位置是否运动过的位置，判断位置是否在禁止位置
            if (lower <= nextPosition && nextPosition <= upper && !visited.contains(nextPosition * nextDirection) && !forbiddenSet.contains(nextPosition)) {
                visited.add(nextPosition * nextDirection);
                queue.offer(new int[]{nextPosition, nextDirection, step + 1});
            }

            // 因为不能连续后退两次，所以只有当前面一次是前进的情况，此时才有后退的可能
            if (direction == 1) {
                // 临时变量，记录位置
                nextPosition = position - b;
                // 临时变量，记录方向
                nextDirection = -1;
                // 判断位置是否在上下界限中，判断位置是否运动过的位置，判断位置是否在禁止位置
                if (lower <= nextPosition && nextPosition <= upper && !visited.contains(nextPosition * nextDirection) && !forbiddenSet.contains(nextPosition)) {
                    visited.add(nextPosition * nextDirection);
                    queue.offer(new int[]{nextPosition, nextDirection, step + 1});
                }
            }
        }
        return -1;
    }

}
